﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include<vector>
#include<string>
#include <queue>

//int main()
//{
//	cout << "hello world" << endl;
//	return 0;
//}

// 二分查找 
class Solution0 {
public:
    int search(vector<int>& nums, int target)
    {
        int len = nums.size() - 1;
        int left = 0, right = len;
        while (left <= right)
        {
            int mid = left + (right - left) / 2;    //防止溢出
            if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
            else
                return mid;
        }
        return  -1;
    }
};

// 二分查找 - 在排序数组中查找元素的第⼀个和最后⼀个位置
class Solution1 {
public:
    vector<int> searchRange(vector<int>& nums, int target)
    {
        //  处理数组为空的情况
        if (nums.size() == 0)
            return { -1, -1 };
        int begin = 0;
        int left = 0, right = nums.size() - 1;
        // 寻找左端点
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)    left = mid + 1;
            else    right = mid;
        }
        if (nums[left] != target)    return { -1,-1 };
        else begin = left;

        left = 0;
        right = nums.size() - 1;
        // 寻找右端点
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target)   right = mid - 1;
            else    left = mid;
        }

        return { begin, left };
    }
};
// 二分查找 - x的算术平方根
class Solution2 {
public:
    int mySqrt(int x)
    {
        if (x < 1) return 0;
        int left = 1, right = x;
        while (left < right)
        {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid > x)   right = mid - 1;
            else left = mid;
        }
        return left;
    }
};

// 二分查找 - 搜索插⼊位置
class Solution3 {
public:
    int searchInsert(vector<int>& nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target)  right = mid - 1;
            else    left = mid;
        }
        if (nums[left] >= target)    return left;
        else    return left + 1;
    }
};

// 二分查找 - 寻找峰值
class Solution4 {
public:
    int peakIndexInMountainArray(vector<int>& arr)
    {
        int left = 0, right = arr.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (arr[mid - 1] > arr[mid]) right = mid - 1;
            else    left = mid;
        }
        return left;
    }
};
// 二分查找 - ⼭峰数组的峰顶
class Solution5 {
public:
    int findPeakElement(vector<int>& nums)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > nums[mid - 1])   left = mid;
            else    right = mid - 1;
        }
        return left;
    }
};

// 二分查找 - 搜索旋转排序数组中的最⼩值
class Solution6
{
public:
    int findMin(vector<int>& nums)
    {
        int left = 0, right = nums.size() - 1;
        int x = nums[right]; // 标记⼀下最后⼀个位置的值
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > x) left = mid + 1;
            else right = mid;
        }
        return nums[left];
    }
};
// 二分查找 - 点名
class Solution7 {
public:
    int takeAttendance(vector<int>& records)
    {
        int left = 0, right = records.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (mid == records[mid])   left = mid + 1;
            else    right = mid;
        }
        if (left == records[left])
            return left + 1;
        else return left;
    }
};

// 前缀和 - 
int main()
{
    // 1 读入数据
    int n = 0, q = 0;
    cin >> n >> q;
    vector<int> arr(n + 1);
    for (int i = 1; i <= n; i++)  cin >> arr[i];
    // 2 预处理dp数组
    vector<long long> dp(n + 1);    // 防止溢出
    for (int i = 1; i <= n; i++)
    {
        dp[i] = dp[i - 1] + arr[i];
    }
    // 3 使用前缀和数组dp
    int l = 0, r = 0;
    for (int i = 0; i < q; i++)
    {
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

// 前缀和 - 二维数组的前缀和
int main()
{
    // 输入数据
    int n = 0, m = 0, q = 0;
    cin >> n >> m >> q;
    vector<vector<int>> vv(n + 1, vector<int>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> vv[i][j];

    // 求前缀和
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + vv[i][j] - dp[i - 1][j - 1];

    //使用前缀和
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    while (q--)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
}

// 前缀和 - 寻找数组的中⼼下标
class Solution {
public:
    int pivotIndex(vector<int>& nums)
    {
        int len = nums.size();
        vector<int> f(len); vector<int> g(len);

        // 前缀和 + 后缀和
        for (int i = 1; i < len; i++)
            f[i] = f[i - 1] + nums[i - 1];
        for (int i = len - 2; i >= 0; i--)
            g[i] = g[i + 1] + nums[i + 1];

        // 使用前后缀和
        for (int i = 0; i < len; i++)
            if (f[i] == g[i])    return i;

        return -1;
    }
};

// 前缀和 - 除⾃⾝以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums)
    {
        int len = nums.size();
        vector<int> f(len); vector<int> g(len);
        // 处理边界问题
        f[0] = g[len - 1] = 1;
        for (int i = 1; i < len; i++)
            f[i] = f[i - 1] * nums[i - 1];
        for (int i = len - 2; i >= 0; i--)
            g[i] = g[i + 1] * nums[i + 1];

        // 使用前缀和
        vector<int> v(len);
        for (int i = 0; i < len; i++)
            v[i] = f[i] * g[i];
        return v;
    }
};

#include <unordered_map>
// 和可被 K 整除的⼦数组
class Solution
{
public:
    int subarraysDivByK(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        hash[0 % k] = 1; // 0 这个数的余数
        int sum = 0, ret = 0;
        for (auto x : nums)
        {
            sum += x; // 算出当前位置的前缀和
            int r = (sum % k + k) % k; // 修正后的余数
            if (hash.count(r)) ret += hash[r]; // 统计结果
            hash[r]++;
        }
        return ret;
    }
};

// 位运算 - 位1的个数
class Solution{
public:
    int hammingWeight(int n)
    {
        int cnt = 0;
        while (n)
        {
            cnt++;
            n &= (n - 1);   // 每次干掉最右边的位1
        }
        return cnt;
    }
};

// 位运算 - 比特位计数
class Solution{
public:
    int hammingWeight(int n)
    {
        int cnt = 0;
        while (n)
        {
            cnt++;
            n &= (n - 1);
        }
        return cnt;
    }
    vector<int> countBits(int n)
    {
        vector<int> v;
        for (int i = 0; i <= n; i++)
            v.push_back(hammingWeight(i));
        return v;
    }
};

// 位运算 - 汉明距离
class Solution {
public:
    int hammingDistance(int x, int y)
    {
        int cnt = 0, res = x ^ y;
        while (res)
        {
            cnt++;
            res = res & (res - 1);
        }
        return cnt;
    }
};
// 位运算 - 只出现一次的数字
class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            ret ^= nums[i];
        }
        return ret;
    }
};

// hasi - 只出现一次的数字3
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)
    {
        vector<int> v;
        unordered_map<int, int> hash;
        for (auto e : nums)
            hash[e]++;
        for (auto e : hash)
        {
            if (e.second == 1)
                v.push_back(e.first);
        }
        return v;
    }
};
// 位运算 - 判断字符是否唯⼀（位图）
class Solution {
public:
    bool isUnique(string astr)
    {
        // 利用鸽巢原理做优化
        if (astr.size() > 26)    return false;
        // 位图
        int bitMap = 0;
        for (auto e : astr)
        {
            int i = e - 'a';
            // 判断字符是否已经出现过
            if (((bitMap >> i) & 1) == 1)    return false;
            // 若没有出现，则把该位置置成1
            bitMap |= 1 << i;
        }
        return true;
    }
};

// 位运算 - 丢失的数字
class Solution {
public:
    // 位运算
    int missingNumber(vector<int>& nums)
    {
        int ret = 0;
        for (auto e : nums)  ret ^= e;
        for (int i = 0; i <= nums.size(); i++)    ret ^= i;
        return ret;
    }
    // 高斯求和
    /*int missingNumber(vector<int>& nums)
    {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++)  sum += nums[i];

        int S = nums.size() * (1 + nums.size()) / 2;
        int ans = S - sum;
        return ans;
    }*/
};

// 位运算 - 两整数之和
class Solution {
public:
    int getSum(int a, int b)
    {
        while (b)
        {
            int x = a ^ b;      //无进位相加
            // 处理进位情况
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = x;          //重新为a，b赋值
            b = carry;
        }
        return a;
    }
};

// 位运算 - 只出现⼀次的数字 II
class Solution {
public:
    int singleNumber(vector<int>& nums)
    {
        int ret = 0;
        for (int i = 0; i < 32; i++)   // 依次去修改ret中的每一位
        {
            int sum = 0;
            for (auto e : nums)      // 计算nums中所有的数的第i位和
                if (((e >> i) & 1) == 1)
                    sum++;
            sum %= 3;
            if (sum == 1) ret |= 1 << i;
        }
        return ret;
    }
};

// 模拟 - 替换所有的问号
class Solution {
public:
    string modifyString(string s)
    {
        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '?')
            {
                for (char ch = 'a'; ch <= 'z'; ch++)
                {
                    if ((i == 0 || ch != s[i - 1]) && (i == s.size() - 1 || ch != s[i + 1]))
                    {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};
// 模拟 - 提莫攻击
class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration)
    {
        int res = 0;
        for (int i = 1; i < timeSeries.size(); i++)
        {
            int sub = timeSeries[i] - timeSeries[i - 1];
            if (sub >= duration)
                res += duration;
            else res += sub;
        }
        return res + duration;
    }
};

// 模拟 - N 字形变换
class Solution
{
public:
    string convert(string s, int numRows)
    {
        // 处理边界情况
        if (numRows == 1) return s;
        string ret;
        int d = 2 * numRows - 2, n = s.size();
        // 1. 先处理第⼀⾏
        for (int i = 0; i < n; i += d)
            ret += s[i];
        // 2. 处理中间⾏
        for (int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏
        {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d)
            {
                if (i < n) ret += s[i];
                if (j < n) ret += s[j];
            }
        }
        // 3. 处理最后⼀⾏
        for (int i = numRows - 1; i < n; i += d)
            ret += s[i];
        return ret;
    }
};
// 模拟 - 外观数列
class Solution {
public:
    string countAndSay(int n)
    {
        string res = "1";
        for (int i = 1; i < n; i++)
        {
            string tmp = "";
            for (int left = 0, right = 0; right < res.size();)
            {
                while (right < res.size() && res[left] == res[right])
                    right++;
                tmp += to_string(right - left) + res[left];
                left = right;
            }
            res = tmp;
        }
        return res;
    }
};

// 分治 - 颜⾊分类
class Solution
{
public:
    void sortColors(vector<int>& nums)
    {
        int n = nums.size();
        int left = -1, right = n, i = 0;
        while (i < right)
        {
            if (nums[i] == 0) swap(nums[++left], nums[i++]);
            else if (nums[i] == 1) i++;
            else swap(nums[--right], nums[i]);
        }
    }
};

// 分治 - 快速排序
class Solution {
public:
    // 获取随机数
    int getRanDom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
    // 快排
    void qsort(vector<int>& nums, int l, int r)
    {
        if (l >= r)  return;
        // 获取随机数
        int key = getRanDom(nums, l, r);
        // 分三步分别讨论
        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] < key)      swap(nums[++left], nums[i++]);
            else if (nums[i] == key) i++;
            else    swap(nums[--right], nums[i]);
        }
        // 递归排 左区间和右区间
        // [l, left] [left + 1, right - 1] [right, r];
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(NULL));  // 种下随机数种子
        // 快排
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};
// 快速选择算法 - 数组中的第K个最大元素
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(NULL));
        int n = nums.size();
        qsort(nums, 0, n - 1);

        return nums[n - k];
    }
    void qsort(vector<int>& nums, int l, int r)
    {
        if (l > r)   return;
        int key = GetRandom(nums, l, r);
        int index = l, left = l - 1, right = r + 1;
        while (index < right)
        {
            if (key > nums[index])   swap(nums[++left], nums[index++]);
            else if (key == nums[index]) index++;
            else    swap(nums[--right], nums[index]);
        }
        // [l, left][left + 1, right - 1][right, r]
        qsort(nums, l, left);
        qsort(nums, right, r);
    }
    int GetRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
};
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        priority_queue<int> pq(nums.begin(), nums.end());

        while (k - 1)
        {
            pq.pop();
            k--;
        }
        return pq.top();
    }
};

// 快排 - 库存管理3
// 堆
class Solution {
public:
    struct Compare
    {
        bool operator()(const int x, const int y)
        {
            return x > y;
        }
    };
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        priority_queue<int, vector<int>, Compare> pq(stock.begin(), stock.end());
        vector<int> v;
        int x = 0;
        while (!pq.empty() && x < cnt)
        {
            v.emplace_back(pq.top());
            pq.pop();
            x++;
        }
        return v;
    }
};
// 快排
class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        srand(time(NULL));
        vector<int> v;
        qsort(stock, 0, stock.size() - 1);

        for (int i = 0; i < cnt; i++)
            v.emplace_back(stock[i]);
        return v;
    }
    void qsort(vector<int>& stock, int l, int r)
    {
        if (l >= r)  return;
        int key = GetRandom(stock, l, r);
        int index = l, left = l - 1, right = r + 1;
        while (index < right)
        {
            if (stock[index] < key)  swap(stock[++left], stock[index++]);
            else if (stock[index] == key)    index++;
            else    swap(stock[--right], stock[index]);
        }
        // [l, left][left + 1, right - 1][right, r]
        qsort(stock, l, left);
        qsort(stock, right, r);
    }
    int GetRandom(vector<int>& stock, int left, int right)
    {
        return stock[rand() % (right - left + 1) + left];
    }
};
// 分治 - 归并
class Solution {
    vector<int> v;
public:
    vector<int> sortArray(vector<int>& nums)
    {
        v.resize(nums.size());
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right)   return;

        int mid = left + (right - left) / 2;
        //  [left, mid][mid + 1, right]
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        int index = left, cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
            v[index++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        while (cur1 <= mid)
            v[index++] = nums[cur1++];
        while (cur2 <= right)
            v[index++] = nums[cur2++];

        for (int i = left; i <= right; ++i)
            nums[i] = v[i];
    }
};
// 分治 - 归并_数组中的逆序对
class Solution
{
    int tmp[50001];
public:
    int reversePairs(vector<int>& nums)
    {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    int mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right)   return 0;

        int ret = 0;
        // 1.找中间点，将数组分为两部分
        int mid = (left + right) >> 1;
        // [left, mid][mid + 1, right]
        // 2.左边逆序对的个数 + 排序 + 右边逆序对的个数 + 排序
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 3.一左一右的个数
        int i = left, cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
        {
            if (nums[cur1] <= nums[cur2])
                tmp[i++] = nums[cur1++];
            else
            {
                ret += (mid - cur1 + 1);
                tmp[i++] = nums[cur2++];
            }
        }
        // 4. 处理一下排序
        while (cur1 <= mid)  tmp[i++] = nums[cur1++];
        while (cur2 <= right)  tmp[i++] = nums[cur2++];

        for (int j = left; j <= right; j++)
            nums[j] = tmp[j];

        return ret;
    }
};
// 分治 - 翻转对
class Solution
{
    int tmp[50010];
public:
    int reversePairs(vector<int>& nums)
    {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    int mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right)   return 0;

        int ret = 0;
        int mid = (left + right) >> 1;
        // [left, mid][mid + 1, right]
        // 计算左右两侧的翻转对
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 先计算翻转对的数量
        int cur1 = left, cur2 = mid + 1, i = left;
        while (cur1 <= mid)
        {
            while (cur2 <= right && nums[cur2] >= nums[cur1] / 2.0)
                cur2++;
            if (cur2 > right)    break;
            ret += right - cur2 + 1;
            cur1++;
        }
        // 合并两个有序数组
        cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];
        while (cur1 <= mid)
            tmp[i++] = nums[cur1++];
        while (cur2 <= right)
            tmp[i++] = nums[cur2++];

        for (int j = left; j <= right; j++)
            nums[j] = tmp[j];

        return ret;
    }
};